package pers.qianyu.month_202101.date_20210111;

import org.junit.*;
import pers.qianyu.util.*;

import java.util.*;

/**
 * 542. 01 矩阵
 * https://leetcode-cn.com/problems/01-matrix/
 * - 多元广度优先搜索
 *
 * @author mizzle rain
 * @date 2021-01-11 20:38
 */
public class UpdateMatrix {
    int[][] dxy = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public int[][] updateMatrix(int[][] matrix) {
        int h = matrix.length;
        if (h == 0) return new int[0][0];
        int w = matrix[0].length;
        if (w == 0) return new int[0][0];
        int[][] res = new int[h][w];
        boolean[][] visited = new boolean[h][w];

        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == 0) {
                    q.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] arr = q.poll();
            for (int[] d : dxy) {
                int x = arr[0] + d[0], y = arr[1] + d[1];
                if (x >= 0 && y >= 0 && x < h && y < w && !visited[x][y]) {
                    res[x][y] = res[arr[0]][arr[1]] + 1;
                    q.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }

        return res;
    }

    @Test
    public void test1() {
        int[][] matrix = {
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1}
        };
        int[][] res = new UpdateMatrix().updateMatrix(matrix);
        ArrayUtil.printDeepToString(res);
    }

    @Test
    public void test2() {
        int[][] matrix = {
                {1, 1, 0, 0, 1, 0, 0, 1, 1, 0},
                {1, 0, 0, 1, 0, 1, 1, 1, 1, 1},
                {1, 1, 1, 0, 0, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 1, 1},
                {0, 0, 1, 1, 1, 1, 1, 1, 1, 0},
                {1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
                {0, 1, 1, 1, 1, 1, 1, 0, 0, 1},
                {1, 1, 1, 1, 1, 0, 0, 1, 1, 1},
                {0, 1, 0, 1, 1, 0, 1, 1, 1, 1},
                {1, 1, 1, 0, 1, 0, 1, 1, 1, 1}
        };
        int[][] res = new UpdateMatrix().updateMatrix(matrix);
        ArrayUtil.printDeepToString(res);
    }
}
